//
// Description: 5849. 好子集的数目
// Created by Loading on 2021/9/5.
//

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int numberOfGoodSubsets(vector<int> &nums) {
    constexpr int MOD = 1e9 + 7;
    // 每个数出现的次数
    int cnt[31] = {0};
    // g[i][j] = true 表示 i 和 j 的最大公约数大于 1
    bool g[31][31] = {false};
    // status[i] = true 表示 i 不可选择
    bool status[31] = {false};

    // 预处理
    for (auto &x : nums) {
        cnt[x]++;
    }
    // nums 中 1 的选择方法数
    int C = 1;
    for (int i = 0; i < cnt[1]; ++i) {
        C = C * 2 % MOD;
    }

    for (int i = 1; i <= 30; ++i) {
        for (int j = 1; j <= 30; ++j) {
            if (gcd(i, j) > 1) {
                // i，j 的最大公约数大于 1
                g[i][j] = true;
            }
        }
    }
    for (int i = 2; i * i <= 30; ++i) {
        for (int j = 1; j * i * i <= 30; ++j) {
            // 平方数或平方数的倍数，不可选择
            status[j * i * i] = true;
        }
    }

    // 当前已选择的数集合
    vector<int> path;
    function<int(int, int)> dfs = [&](int pos, int sum) {
        if (sum == 0) {
            return 0;
        }
        if (pos > 30) {
            // 不可以一个都不选择
            if (path.empty()) {
                return 0;
            }
            return (int) (sum * (LL) C % MOD);
        }

        // 不选择当前元素
        int res = dfs(pos + 1, sum);
        // 当前元素可选择
        if (!status[pos]) {
            // 与当前已选择的数的集合判断最大公约数
            bool chose = true;
            for (auto &x : path) {
                if (g[x][pos]) {
                    chose = false;
                    break;
                }
            }
            // 可以选择
            if (chose) {
                path.emplace_back(pos);
                res = (res + dfs(pos + 1, sum * (LL) cnt[pos] % MOD)) % MOD;
                // 回溯
                path.pop_back();
            }
        }

        return res;
    };

    return dfs(2, 1) % MOD;
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    int res = numberOfGoodSubsets(nums);
    cout << res << endl;

    return 0;
}